A growing interest exists among service providers to offer their customers new revenue-generating services with Quality of Service (QoS) guarantees. This is facilitated by current efforts to provide resource reservations and explicit path routing, e.g., MultiProtocol Label Switching (MPLS).
On the other hand, physical network infrastructures may be prone to failures. For example, in optical networks, a single link failure is frequent enough in order to warrant consideration (see, e.g., Iraschko, et al., “A Highly Efficient Path-Restoration Protocol for Management of Optical Network Transport Integrity,” IEEE Journal on Selected Areas in Communications, 18(5):779-793, May 2000).
Therefore, a key requirement for such services is that they also be resilient to failures. This goal, namely, providing QoS paths with failure resilience, can be achieved by provisioning primary and restoration paths that satisfy the QoS constraints. The primary QoS path is used during normal network operation; upon failure of a network element (node or link) in the primary path, the traffic is immediately switched to a restoration path. To facilitate this seamless recovery to a restoration path in the event of a failure, it is necessary to reserve network resources (e.g., bandwidth) on both the primary and restoration QoS paths. Such resources should be consumed in a network-wide efficient manner.
A common way for modeling the impact of such resource consumption on each link is by associating “costs” with the links. Accordingly, a major problem is to find primary and restoration paths that satisfy end-to-end QoS constraints at minimum cost. This problem is the subject of this study.
QoS constraints occur naturally in a number of practical settings involving bandwidth and delay sensitive applications such as voice over IP, audio and video conferencing, multimedia streaming etc. QoS constraints can be divided into bottleneck constraints, such as bandwidth and additive constraints, such as delay or jitter.
QoS routing has been the subject of several recent studies and proposals (see, e.g., Crawley, et al., “A Framework for QoS-based Routing in the Internet—RFC No. 2386,” Internet RFC, August 1998; Ma, et al., “Quality of Service Routing for Traffic with Performance Guarantees,” in Proceedings of International Workshop on Quality of Service (IWQoS '97), Columbia University, New York, N.Y., May 1997; Orda, “Routing With End to End QoS Guarantees in Broadband Networks,” IEEE/ACM Transactions on Networking, 7(3):365-374, June 1999; Sobrinho, “Algebra and Algorithms for QoS Path Computation and Hop-by-Hop Routing in the Internet,” in Proceedings of IEEE INFOCOM 2001, Anchorage, AK, April 2001; and references therein). However, none of the prior studies on QoS routing consider the problem of provisioning QoS paths with restoration.
Similarly, path restoration and routing over alternate paths has also attracted a large body of research (see, e.g., Italiano, et al., “Restoration Algorithms for Virtual Private Networks in the Hose Model,” in Proceedings of IEEE INFOCOM 2002, New York, N.Y., June 2002; Kar, et al., “Routing Restorable Bandwidth Guaranteed Connections using Maximum 2-Route Flows,” in Proceedings of IEEE INFOCOM 2002, New York, N.Y., June 2002; Kodialam, et al., “Dynamic Routing of Bandwidth Guaranteed Tunnels with Restoration,” in Proceedings of IEEE INFOCOM 2000, Tel-Aviv, Israel, March 2000; Krishna, et al., “A Segmented Backup Scheme for Dependable Real Time Communication in Multihop Networks,” in Proceedings of Workshop on Parallel and Distributed Real-Time Systems (WPDRTS 2000), Cancun, Mexico, May 2000; and Li, et al., “Efficient Distributed Path Selection for Shared Restoration Connections,” In Proceedings of IEEE INFOCOM 2002, New York, N.Y., June 2002, all incorporated herein by reference). Most of the proposed solutions, however, consider only bottleneck QoS constraints. The few studies that do consider additive constraints, focus on heuristic approaches and do not provide proven performance guarantees.
Bottleneck QoS constraints can be efficiently handled by pruning infeasible links. However, additive QoS constraints are more difficult to handle. Indeed, the basic problem of finding an optimal path that satisfies an additive QoS constraint is NP-hard (see, e.g., Garey, et al., Computers and Intractability, Freeman, San Francisco, Calif. 1979). Moreover, it turns out that, in the presence of additive QoS constraints, the widely used approach of disjoint primary and restoration paths is not an optimal strategy.
Accordingly, what is needed in the art are systems and methods for provisioning Quality of Service (QoS) paths with restoration for use in networks that handle both bottleneck and additive QoS constraints and that are most preferably computationally efficient, so paths can be computed and recovered in real-time.